package dataStructStack;

import java.util.Stack;

public class testLeeCoNiuKe {

    public int evalRPN(String[] tokens) {

        Stack<Integer> stack = new Stack<>();

        for (String x: tokens) {
            if( !isOperation(x) ){
                stack.push(Integer.parseInt(x));
            }else {
                //  num1 +-*/ num2
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (x){
                    case "+": stack.push(num1+num2);break;
                    case "-": stack.push(num1-num2);break;
                    case "*": stack.push(num1*num2);break;
                    case "/": stack.push(num1/num2);break;
                }
            }
        }
        return stack.pop();



    }
    //  判断 是否是运算符
    public boolean isOperation(String x){
        if(x.equals("+") || x.equals("-") ||x.equals("*")|| x.equals("/") ){
            return true;
        }
        return  false;
    }

    public boolean isValid(String s) {

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(ch == '(' ||ch == '{' ||ch == '[' ){
                stack.push(ch);
            }else {
                if(stack.empty()){
                    return false;
                }
                char ch2 = stack.peek();  // ch2 此时是左括号
                if(ch == ')' && ch2 == '(' ||ch == '}' && ch2 == '{' ||ch == ']' && ch2 == '['  ){
                    stack.pop();
                }else {
                    return false;   //   不匹配
                }
            }
        }
        if(stack.empty()){
            return true;
        }
        return false;

    }


    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here

        if(pushV == null){
            return false;
        }
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);
            while ( j < popV.length && !stack.empty() && stack.peek().equals(popV[j])  ){
                stack.pop();
                j++;
            }
        }

        if( stack.empty()){
            return true;
        }
        return false;
    }

}

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;
    public MinStack() {
        stack = new Stack();
        minStack = new Stack();
    }

    public void push(int val) {
        stack.push(val);
        if(minStack.empty()){
            minStack.push(val);
        }
        else {
            if( val <= minStack.peek() ){
                minStack.push(val);
            }
        }
    }

    public void pop() {
        if( !stack.empty()){
            if( stack.pop().equals(minStack.peek())  ){
                minStack.pop();
            }
        }
    }

    public int top() {
        if( !stack.empty() ){
            stack.peek();
        }
        return -1;
    }

    public int getMin() {
        return minStack.peek();
    }
}
